package Greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 零钱兑换问题
 * 从这个题我们来分析贪心算法的特点：
 *      注意当我们选则的coins = 1,5,10,25    money = 41
 *      此时我们使用贪心算法可以得到全局最优解 四枚硬币 1 5 10 25
 *      但是当我们更换我们的coins数组为 [1,5,20,25] money = 41
 *      如果还是按照贪心算法我们得到的结果为 25 5 5 5 1 此时需要五枚硬币
 *      但是我们一眼可以看出全局最优解为 20 20 1
 *      由此我们可以直到由贪心算法得到的解并不能作为全局最优解，所以为了得到全局最优解我们需要
 *      对贪心算法做一些改进，从而得到全局的最优解
 *
 *      贪心算法：简单，快速，不需要穷举出所有的情况，一般作为其他算法的辅助策略
 *      缺点：我们仅仅只能得到局部解，我们可以使用动态规划得到全局最优解
 *
 *
 *
 *
 */
@SuppressWarnings("all")
public class 零钱兑换 {
    public static void main(String[] args) {
        int[] coins = {1,5,10,25};
        coinChange(43,coins);
    }

    /**
     * 零钱兑换问题         此题也是典型的贪心算法求解问题
     * 注意：零钱数组中的零钱面值可以重复使用
     * @param money:总钱数
     * @param coins:零钱数组
     */
    public static void coinChange(int money,int[] coins) {
        int count = 0; // 记录最终使用的最少的零钱数量
        List<Integer> coin_var = new ArrayList<>(); // 记录选择的零钱种类
        Arrays.sort(coins); // 对数组进行排序从下到大
        if (money < coins[0]) {
            System.out.println("无法换零钱");
            return;
        }
        for (int i = coins.length - 1; i >= 0; i--) {
            if (money < coins[i]) {
                continue;
            }
            while (money >= coins[i]) {
                money -= coins[i];
                count++;
                coin_var.add(coins[i]);
            }
        }
        System.out.println("总共选择的零钱数量："+count);
        System.out.println("具体选择的零钱金额如下：");
        for (Integer integer : coin_var) {
            System.out.print(integer+" ");
        }
    }
}
